Amiga Tools 2

home *** CD-ROM | disk | FTP | other *** search

/ Amiga Tools 2 / Amiga Tools 2.iso / tex / macros / source / contrib / siam / lexample.tex / node6_mn.html < prev next >

Wrap

Text File | 1995-03-09 | 12KB | 230 lines

<H2><A ID="SECTION00021000000000000000"> Numerical experiments</A> </H2> We conducted numerical experiments in computing inexact Newton steps for discretizations of a <#303#>modified Bratu problem<#303#>, given by <DIV ALIGN="CENTER"><A ID="bratu"><tex2html_anchor_mark></A><tex2html_verbatim_mark>#math47# <TABLE CELLPADDING="0" ALIGN="CENTER" WIDTH="100%"> <TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><tex2html_image_mark>#tex2html_wrap_indisplay1381#</TD> <TD WIDTH="10" ALIGN="CENTER" NOWRAP>=</TD> <TD ALIGN="LEFT" NOWRAP>f;SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp;in D,</TD> <TD WIDTH=10 ALIGN="RIGHT"> </TD></TR> <TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"> </TD> <TD> </TD> <TD> </TD> <TD WIDTH=10 ALIGN="RIGHT"> (9)</TD></TR> <TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT">w</TD> <TD WIDTH="10" ALIGN="CENTER" NOWRAP>=</TD> <TD ALIGN="LEFT" NOWRAP>0;SPMnbsp;;SPMnbsp;;SPMnbsp;;SPMnbsp;on ∂D,</TD> <TD WIDTH=10 ALIGN="RIGHT"> </TD></TR> </TABLE></DIV> where c and d are constants. The actual Bratu problem has d = 0 and f≡ 0. It provides a simplified model of nonlinear diffusion phenomena, e.g., in combustion and semiconductors, and has been considered by Glowinski, Keller, and Rheinhardt [#GloKR85#<tex2html_cite_mark>#1##<tex2html_cite_mark>#], as well as by a number of other investigators; see [#GloKR85#<tex2html_cite_mark>#1##<tex2html_cite_mark>#] and the references therein. See also problem 3 by Glowinski and Keller and problem 7 by Mittelmann in the collection of nonlinear model problems assembled by Moré [#More#<tex2html_cite_mark>#1##<tex2html_cite_mark>#]. The modified problem (<A HREF=<tex2html_cr_mark>#bratu#315><tex2html_cr_mark></A>) has been used as a test problem for inexact Newton methods by Brown and Saad [#Brown-Saad1#<tex2html_cite_mark>#1##<tex2html_cite_mark>#]. In our experiments, we took <tex2html_verbatim_mark>#math48#D = [0, 1]×[0, 1], f≡ 0, c = d = 10, and discretized (<A HREF=<tex2html_cr_mark>#bratu#317><tex2html_cr_mark></A>) using the usual second-order centered differences over a <tex2html_verbatim_mark>#math49#100×100 mesh of equally spaced points in D. In <#495#>GMRES<#495#>(m), we took m = 10 and used fast Poisson right preconditioning as in the experiments in §2. The computing environment was as described in §2. All computing was done in double precision. <DIV class="CENTER"><A ID="diff"><tex2html_anchor_mark></A><A ID="469"><tex2html_anchor_mark></A> <TABLE> <CAPTION class="BOTTOM"><#1398#>Figure<#1398#>: <#1399#><#320#> Log<#320#>10 of the residual norm versus the number of <#322#> GMRES(m)<#322#> iterations for the finite difference methods.<#1399#></CAPTION> <TR><TD><tex2html_image_mark>#figure318#</TD></TR> </TABLE> </DIV> In the first set of experiments, we allowed each method to run for 40 <#325#><#496#>GMRES(m)<#496#><#325#> iterations, starting with zero as the initial approximate solution, after which the limit of residual norm reduction had been reached. The results are shown in Fig.~<A HREF=<tex2html_cr_mark>#diff#326><tex2html_cr_mark></A>. In Fig.~<A HREF=<tex2html_cr_mark>#diff#327><tex2html_cr_mark></A>, the top curve was produced by method FD1. The second curve from the top is actually a superposition of the curves produced by methods EHA2 and FD2; the two curves are visually indistinguishable. Similarly, the third curve from the top is a superposition of the curves produced by methods EHA4 and FD4, and the fourth curve from the top, which lies barely above the bottom curve, is a superposition of the curves produced by methods EHA6 and FD6. The bottom curve was produced by method A. In the second set of experiments, our purpose was to assess the relative amount of computational work required by the methods which use higher-order differencing to reach comparable levels of residual norm reduction. We compared pairs of methods EHA2 and FD2, EHA4 and FD4, and EHA6 and FD6 by observing in each of 20 trials the number of <#328#><#497#>GMRES(m)<#497#><#328#> iterations, number of F-evaluations, and run time required by each method to reduce the residual norm by a factor of <tex2html_verbatim_mark>#math50#ε, where for each pair of methods <tex2html_verbatim_mark>#math51#ε was chosen to be somewhat greater than the limiting ratio of final to initial residual norms obtainable by the methods. In these trials, the initial approximate solutions were obtained by generating random components as in the similar experiments in §2. We note that for every method, the numbers of <#329#><#500#>GMRES(m)<#500#><#329#> iterations and F-evaluations required before termination did not vary at all over the 20 trials. The <#330#><#501#>GMRES(m)<#501#><#330#> iteration counts, numbers of F-evaluations, and means and standard deviations of the run times are given in Table <A HREF=<tex2html_cr_mark>#diffstats#331><tex2html_cr_mark></A>. <DIV class="CENTER"> <DIV class="CENTER"> <#483#><A ID="470"><tex2html_anchor_mark></A> <TABLE CELLPADDING=3 BORDER="1"> <CAPTION>Table: Statistics over 20 trials of GMRES(m) iteration numbers, F-evaluations, and run times required to reduce the residual norm by a factor of <tex2html_verbatim_mark>#math52#ε. For each method, the number of GMRES(m) iterations and F-evaluations was the same in every trial.</CAPTION> <TR><TD ALIGN="CENTER"> </TD> <TD ALIGN="CENTER"></TD> <TD ALIGN="CENTER"> Number of </TD> <TD ALIGN="CENTER"> Number of </TD> <TD ALIGN="CENTER"> Mean Run Time </TD> <TD ALIGN="CENTER"> Standard </TD> </TR> <TR><TD ALIGN="CENTER"> Method </TD> <TD ALIGN="CENTER"> <tex2html_verbatim_mark>#math54#ε </TD> <TD ALIGN="CENTER"> Iterations </TD> <TD ALIGN="CENTER"> F-Evaluations</TD> <TD ALIGN="CENTER"> (Seconds) </TD> <TD ALIGN="CENTER"> Deviation </TD> </TR> <TR><TD ALIGN="CENTER"> EHA2 </TD> <TD ALIGN="CENTER"> 10-10 </TD> <TD ALIGN="CENTER"> 26 </TD> <TD ALIGN="CENTER"> 32 </TD> <TD ALIGN="CENTER"> 47.12 </TD> <TD ALIGN="CENTER"> .1048 </TD> </TR> <TR><TD ALIGN="CENTER"> FD2 </TD> <TD ALIGN="CENTER"> 10-10 </TD> <TD ALIGN="CENTER"> 26 </TD> <TD ALIGN="CENTER"> 58 </TD> <TD ALIGN="CENTER"> 53.79 </TD> <TD ALIGN="CENTER"> .1829 </TD> </TR> <TR><TD ALIGN="CENTER"> EHA4 </TD> <TD ALIGN="CENTER"> 10-12 </TD> <TD ALIGN="CENTER"> 30 </TD> <TD ALIGN="CENTER"> 42 </TD> <TD ALIGN="CENTER"> 56.76 </TD> <TD ALIGN="CENTER"> .1855 </TD> </TR> <TR><TD ALIGN="CENTER"> FD4 </TD> <TD ALIGN="CENTER"> 10-12 </TD> <TD ALIGN="CENTER"> 30 </TD> <TD ALIGN="CENTER"> 132 </TD> <TD ALIGN="CENTER"> 81.35 </TD> <TD ALIGN="CENTER"> .3730 </TD> </TR> <TR><TD ALIGN="CENTER"> EHA6 </TD> <TD ALIGN="CENTER"> 10-12 </TD> <TD ALIGN="CENTER"> 30 </TD> <TD ALIGN="CENTER"> 48 </TD> <TD ALIGN="CENTER"> 58.56 </TD> <TD ALIGN="CENTER"> .1952 </TD> </TR> <TR><TD ALIGN="CENTER"> FD6 </TD> <TD ALIGN="CENTER"> 10-12 </TD> <TD ALIGN="CENTER"> 30 </TD> <TD ALIGN="CENTER"> 198 </TD> <TD ALIGN="CENTER"> 100.6 </TD> <TD ALIGN="CENTER"> .3278 </TD> </TR> </TABLE><#483#> </DIV> <A ID="diffstats"><tex2html_anchor_mark></A> </DIV> In our first set of experiments, we took c = d = 10 and used right preconditioning with a fast Poisson solver from <#363#><#504#>FISHPACK<#504#><#363#> [#Swarztrauber-Sweet#<tex2html_cite_mark>#1##<tex2html_cite_mark>#], which is very effective for these fairly small values of c and d. We first started each method with zero as the initial approximate solution and allowed it to run for 40 <#365#><#505#>GMRES(m)<#505#><#365#> iterations, after which the limit of residual norm reduction had been reached. Figure <A HREF=<tex2html_cr_mark>#pdep#366><tex2html_cr_mark></A> shows plots of the logarithm of the Euclidean norm of the residual versus the number of <#367#><#506#>GMRES(m)<#506#><#367#> iterations for the three methods. We note that in Fig.~<A HREF=<tex2html_cr_mark>#pdep#368><tex2html_cr_mark></A> and in all other figures below, the plotted residual norms were not the values maintained by <#369#><#507#>GMRES(m)<#507#><#369#>, but rather were computed as accurately as possible ``from scratch.'' That is, at each <#370#><#508#>GMRES(m)<#508#><#370#> iteration, the current approximate solution was formed and its product with the coefficient matrix was subtracted from the right-hand side, all in double precision. It was important to compute the residual norms in this way because the values maintained by <#371#><#509#>GMRES(m)<#509#><#371#> become increasingly untrustworthy as the limits of residual norm reduction are neared; see [#Walker88#<tex2html_cite_mark>#1##<tex2html_cite_mark>#]. It is seen in Fig.~<A HREF=<tex2html_cr_mark>#pdep#373><tex2html_cr_mark></A> that Algorithm EHA achieved the same ultimate level of residual norm reduction as the FDP method and required only a few more <#374#><#510#>GMRES(m)<#510#><#374#> iterations to do so. <DIV class="CENTER"><A ID="pdep"><tex2html_anchor_mark></A><A ID="474"><tex2html_anchor_mark></A> <TABLE> <CAPTION class="BOTTOM"><#1495#>Figure<#1495#>: <#1496#><#377#> Log<#377#>10 of the residual norm versus the number of <#379#> GMRES<#379#>(m) iterations for c = d = 10 with fast Poisson preconditioning. Solid curve: Algorithm <#380#> EHA<#380#>; dotted curve: <#381#> FDP<#381#> method; dashed curve: <#382#> FSP<#382#> method.<#1496#></CAPTION> <TR><TD><tex2html_image_mark>#figure375#</TD></TR> </TABLE> </DIV> In our second set of experiments, we took c = d = 100 and carried out trials analogous to those in the first set above. No preconditioning was used in these experiments, both because we wanted to compare the methods without preconditioning and because the fast Poisson preconditioning used in the first set of experiments is not cost effective for these large values of c and d. We first allowed each method to run for 600 <#385#><#511#>GMRES(m)<#511#><#385#> iterations, starting with zero as the initial approximate solution, after which the limit of residual norm reduction had been reached.